package com.gaogzhen.datastructure.queue;

import java.io.Serializable;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 堆
 *  根据传入比较器，判断是最大堆还是最小堆
 *      默认为最大堆
 *      (o1,o2) -> {o2.compareTo(o1)} 最小堆
 *
 * @author Administrator
 * @date 2022-12-03 20:41
 */
public  class HeapPriorityQueue<E extends Comparable<E>> implements Queue<E>, Serializable {

    /**
     * 存放元素容器
     */
    private final E[] table;

    /**
     * 元素个数
     */
    private int size;

    /**
     * 比较器
     */
    private final Comparator<E> comparator;

    /**
     * 构造器
     * @param initialCapacity   初始容量
     */
    public HeapPriorityQueue(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        table = (E[]) new Comparable[initialCapacity + 1];
        comparator = Comparable::compareTo;
    }

    /**
     * 构造器
     * @param initialCapacity   初始容量
     * @param comparator        比较器
     */
    public HeapPriorityQueue(int initialCapacity, Comparator<E> comparator) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        table = (E[]) new Comparable[initialCapacity + 1];
        this.comparator = comparator == null ? Comparable::compareTo: comparator;
    }

    /**
     * 插入元素
     * @param e 元素
     */
    @Override
    public void offer(E e) {
        if (size + 1 > table.length - 1) {
            throw new IndexOutOfBoundsException();
        }
        table[++size] = e;
        swim(size);
    }

    /**
     * 返回堆顶元素
     * @return  堆顶元素
     */
    @Override
    public E peek() {
        return table[1];
    }

    /**
     * 弹出堆顶元素
     * @return 堆顶元素
     */
    @Override
    public E poll() {
        if (size <= 0) {
            throw new NoSuchElementException("堆为空");
        }
        E e = table[1];
        table[1] = table[size--];
        table[size + 1] = null;
        sink(1);
        return e;
    }

    /**
     * 判断堆是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取堆中元素个数
     * @return  堆中元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 暂时不做实现
     * @return
     */
    @Override
    public Iterator<E> iterator() {
        return null;
    }

    /**
     * 比较所有i，j出元素大小
     * @param i 所有i
     * @param j 索引j
     * @return 所有i处元素小于索引j处元素返回true；否则返回false
     */
    private boolean compare(int i, int j) {
        return comparator.compare(table[i], table[j]) < 0;
    }

    /**
     * 交换元素
     * @param i 索引i
     * @param j 索引j
     */
    private void exch(int i, int j) {
        E t = table[i];
        table[i] = table[j];
        table[j] = t;
    }

    /**
     * 上浮
     * @param k 上浮元素索引
     */
    private   void swim(int k) {
        while (k > 1 && compare(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    /**
     * 下沉
     * @param k 下沉元素索引
     */
    private  void sink(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            if (j < size && compare(j, j + 1)) j++;
            if (!compare(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    public void show() {
        System.out.println(Arrays.toString(table));
    }

}
